1. Field of the Invention
The present invention relates to a method of processing a figure and a recorded medium. More particularly, the present invention relates to a graphic method of judging intersection of trapezoidal figures in a step of synthesizing a masking layer in the production of large-scale integrated circuits (LSTs).
2. Description of the Related Art
Fabrication of an LSI includes a step of synthesizing a masking layer. Synthesis of the masking layer is a xe2x80x9cgraphic ORxe2x80x9d process for synthesizing design data with the layer as a unit and removing portions where the figures overlap. There can be further exemplified xe2x80x9cAND processingxe2x80x9d, xe2x80x9cNOT processingxe2x80x9d and xe2x80x9cXOR processingxe2x80x9d in addition to OR processing. The data in the masking layer are expressed as a trapezoid, having parallel upper side and lower side, as a unit. Therefore, figures that are to receive the logical processing, such as OR processing, are trapezoidal figures which are basic figures.
The trapezoidal figures to be put to the logic processing are those figures that overlap one upon the other or are those figures in which one figure is completely included in the other figure. Prior to executing the logic processing, therefore, it is necessary to execute an intersection judgement process concerning whether the trapezoidal figures overlap one upon the other (including one figure being completely included in the other figure as described above).
When it is required to judge the intersecting relationship among a plurality of figures (whether they are overlapping, or whether one figure is completely included in the other figure) as in the step of synthesizing the masking layer, the intersection judgement processing has heretofore been executed for every combination of two figures.
According to the conventional intersection judgement processing executed for every combination of two figures, however, the intersection is judged even for those figures that are located at distant positions on a plane of an X-Y coordinate system on which trapezoidal figures are placed, wastefully consuming processing time and requiring an extended period of time for judging the intersecting relationships of all figures.
A key point for executing the graphic method for judging the intersecting relationship at high speed is to reduce the number of times of executing the intersection judgement processing as much as possible.
An object of the present invention is to solve the above-mentioned problem and to provide a graphic method capable of judging, at high speed, the intersecting relationships among large number of figures in the synthesis of a masking layer.
In order to solve the above-mentioned problem, the present invention provides a graphic method of judging intersecting relationships among a plurality of trapezoidal figures, having upper and lower sides in parallel with an X-axis, comprising:
a grouping step for classifying those trapezoidal figures having the lower sides of the same Y-coordinate values into the same groups, sorting the groups based on the Y-coordinate values of said lower sides, sorting the trapezoidal figures included in said groups based on minimum X-coordinate values of the trapezoidal figures, and storing them;
a to-be-judged group-determining step for using any one of said groups as a to-be-judged group in order of sorting;
an intra-group judging step for using any one of said trapezoidal figures included in said to-be-judged group as a to-be-judged figure in order of sorting, using any one of the trapezoidal figures in said to-be-judged group sorted after said to-be-judged figure as a to-be-compared figure successively in order of sorting, and repetitively executing intersection judgement processing only when a maximum X-coordinate value of the to-be-judged figure is greater than a minimum X-coordinate value of the to-be-compared figure while comparing the maximum X-coordinate value of the to-be-judged figure with the minimum X-coordinate value of said to-be-compared figure until the maximum X-coordinate value of the to-be-judged figure becomes smaller than the minimum X-coordinate value of the to-be-compared figure or until the to-be-compared figure disappears; and
an inter-group judging step for using any one of said groups sorted before said to-be-judged group as a to-be-compared group in order of sorting, comparing the Y-coordinate values of the lower sides of the trapezoidal figures included in said to-be-judged group with a maximum Y-coordinate value of a trapezoidal figure included in said to-be-compared group, and executing the intersection judgement processing between the trapezoidal figures included in said to-be-judged group and the trapezoidal figures included in said to-be-compared group only when the Y-coordinate value of the lower side of said to-be-judged group is smaller than said maximum Y-coordinate value of said to-be-compared group;
said to-be-judged group-determining step through up to said inter-group judging step being repeated until there is no group that can be used as said to-be-judged group in said to-be-judged group-determining step.
In the intra-group judging step, the time-consuming intersection judgement processing is not executed for the figures from the first time but, instead, a maximum X-coordinate value of a to-be-judged figure is compared with a minimum X-coordinate value of a to-be-compared figure, which is easy to execute, and the intersection judgement processing is executed only when the maximum X-coordinate value of the to-be-judged figure is larger than the minimum X-coordinate value of the to-be-compared figure, i.e., only when there is a probability of intersection. Therefore, the intersection judgement processing is not executed for the figures which apparently have no probability of intersection. similarly, further, the intersection judgement processing is terminated in the to-be-judged group when the maximum X-coordinate value of the to-be-judged figure becomes smaller than the minimum X-coordinate value of the to-be-compared figure and there is apparently no probability of intersection. Thus, the processing time can be shortened as compared with when the intersection judgement processing is executed for all of the figures in the to-be-judged group.
In the inter-group judging step, further, a Y-coordinate value of the lower side of a trapezoidal figure included in the to-be-judged group is compared with a maximum Y-coordinate value of a trapezoidal figure included in the to-be-compared group, which is easy to process, at the time of judging the intersection between the two groups, i.e., between trapezoidal figure in the to-be-judged group and the trapezoidal figure in the to-be-compared group, and the intersection judgement processing is executed between the trapezoidal figure included in the to-be-judged group and the trapezoidal figure included in the to-be-compared group only when the Y-coordinate value of the lower side of the to-be-judged group is smaller than the maximum Y-coordinate value of the to-be-compared group, i.e., only when there is a probability of intersection. Therefore, the intersection judgement processing is not executed for the trapezoidal figures included in the groups which apparently have no probability of intersection Thus, the processing time can be shortened as compared with when the intersection judgement processing is executed for all of the trapezoidal figures included in the two groups.
In the present invention, further, the inter-group judging step uses any one of the trapezoidal figures included in the to-be-judged group as a to-be-judged figure successively in order of sorting, uses any one of the trapezoidal figures included in the to-be-compared group as a to-be-compared figure successively in order of sorting when the Y-coordinate value of the lower side of the to-be-judged group is smaller than a maximum Y-coordinate value of the to-be-compared group, judges the intersecting relationship between the to-be-judged figure and the to-be-compared figure along the direction of X-axis, judges whether the maximum Y-coordinate value of the to-be-compared figure is greater than the Y-coordinate value of the lower side of the to-be-judged group only when there is a probability of intersection, and executes the intersection judgement processing between the to-be-judged figure and the to-be-compared figure only when the maximum Y-coordinate value of the to-be-compared figure is greater than the Y-coordinate value of the lower side of the to-be-judged group.
According to the invention, further, the probability of intersection is judged between the to-be-judged figure and the to-be-compared figure, which is easy to process, it is judged whether the maximum Y-coordinate value of the to-be-compared figure exceeds the Y-coordinate value of the lower side of the to-be-judged group, i.e., the probability of intersection is judged along the direction of Y-axis prior to executing the intersection judgement processing for the to-be-judged figures in the to-be-judged groups and for the to-be-compared figures in the to-be-compared groups, and the intersection judgement processing is executed only when there is a probability of intersection. Therefore, the intersection judgement processing is not executed for the to-be-judged figures and the to-be-compared figures that apparently have no probability of intersection.
In the invention, further, a to-be-compared figure that is compared first with a to-be-judged figure in the inter-group judging step is a trapezoidal figure which is sorted first among the trapezoidal figures in the to-be-compared group that is judged for its intersecting relationship with a to-be-judged figure just preceding said to-be-judged figure, but excluding those trapezoidal figures of which maximum X-coordinate values are smaller than the minimum X-coordinate value of the to-be-judged figure.
Thus, according to the invention, the intersecting relationship is not judged for all trapezoidal figures included in a to-be-compared group concerning the trapezoidal figures included in the to-be-judged group. Instead, when there are trapezoidal figures of which maximum X-coordinate values are smaller than the minimum X-coordinate value of the to-be-judged figure among the trapezoidal figures in the to-be-compared group which is judged for its intersecting relationship with a to-be-judged figure just preceding the above to-be-judged figure, these trapezoidal figures and the trapezoidal figures included in the to-be-compared group and sorted earlier than the above trapezoidal figures, are not judged for their intersecting relationship. Therefore, the number of times of the intersection judgement processing can be decreased, and the processing time can be shortened.